package style.zcyLeetCode.b_0001_KMP类;

/**
 * KMP算法
 */
public class Kmp {
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1 = 0; // str1 中比对的位置
        int i2 = 0; // str2 中比对的位置

        int[] next = getNextArray(str2); // 获取最长前缀

        // 保证 i1 i2 不越界
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {  // 位置值相等
                i1++;
                i2++;
            } else if (next[i2] == -1) {  // i2 == 0 或者 next[i2] == -1 表示0位置（ str2中比对的位置已经无法往前跳了 ）
                i1++; // str1 换个开头重新配
            } else {  // 表示i2的next还能往前跳
                i2 = next[i2];
            }
        }
        // i1 越界 或者 i2 越界
        return i2 == str2.length ? i1 - i2 : -1;
    }

    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        // 人为设置 next[0]  next[1]
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;  // 表示拿哪个位置的字符跟 i-1 的比
        while (i < next.length) {
            if (ms[i - 1] == ms[cn]) {
                /*
                 * next[i] = cn+1
                 * i++
                 * cn++
                 */
                next[i++] = ++cn;
            } else if (cn > 0) {
                // 当前跳到 cn 位置的字符，和 i-1 位置的字符配不上，并且cn还能往前跳
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(getIndexOf("abcabcababaccc", "ababa"));
    }
}
